The present invention is directed to the art of image processing and, more particularly, to a method and device for improving pixel block classification schemes by post-processing individual pixels to selectively override halftone classification in blocks of pixels that extend across classification boundaries in a digital image. The present invention will be described in connection with digital printers but finds application in a wide range of other environments and applications including anywhere blocks of digital image pixels are segmentated or classified.
In the reproduction of images from an original document or images from video image data, and more particularly, to the rendering of image data representing an original document that has been electronically scanned, one problem that arises is the limited reflectance domain resolution capabilities of the equipment because most output devices are binary or require compression of the data into binary form for storage efficiency. This is particularly evident when attempting to reproduce halftones, lines, and continuous tone (contone) images. An image data processing system may be tailored so as to offset the limited reflectance domain resolution capabilities of the rendering apparatus. This tailoring, however, is difficult due to the divergent processing needs required by different images which may be encountered by the rendering device. In this respect, it should be understood that the image content of the original document typically consists of multiple image types. The image types include halftones of various frequencies, continuous tones (contones), line copy, text, error diffused images, dithered areas, dot patterns or combinations of any of the above together with some unknown degree of some or all of the above or additional image types.
In view of the situation, optimizing the image processing system for one image type in an effort to offset the limitations in the resolution and the depth capability of the rendering apparatus may not be possible, requiring a compromised choice which may not produce acceptable results. Thus, where a system is optimized for low frequency halftones, it is often at the expense of degraded rendering of high frequency halftones, or of line copy, text, and vice-versa.
To address this particular situation, prior art devices have utilized automatic image segmentation to serve as a tool to identify different image types or imagery. For example, in one such system, image segmentation was used to apply a function to the video image signal, the output of which was used to instruct the image processing system as to the type of image data present so that it could be processed appropriately. In particular, auto-correlation functions were applied to a stream of pixel data to detect the existence and estimate the frequency of halftone image data. These prior methods automatically process a stream of image pixels representing unknown combinations of high and low frequency halftones, contones, text, and/or lines. The auto-correlation function was applied to the stream of image pixels, and for the portions of the stream that contain high frequency halftone image data, the function produced a large number of closely spaced peaks in the resulting signal.
In another auto-segmentation process, an auto-correlation function is calculated for the stream of halftone image data at selected time delays which are predicted to be indicative of the image frequency characteristics, without prior thresholding. Valleys in the resulting auto-correlated function are detected to determine whether a high frequency halftone image is present.
One such example of a prior art automatic segmentation method and device is described in U.S. Pat. No. 5,293,430, the teachings of which are incorporated herein by reference. The basic system of that patent as shown in FIG. 1 is made up of three primary modules. Input information stored in a data buffer 10 is simultaneously directed to an image property classifying section 12, the first primary module, and an image processing section 14, the second primary module. The image property classifying section 12 is made up of any number of sub-modules, but preferably includes at least an auto-correlator 16 and a discriminator 18, which determine whether a block of image pixels stored in the data buffer 10 is one type of imagery or another such as, for example, high or low frequency halftone, line, text, or contone image types.
In parallel with the image property classifying section 12, the image processing section 14 is made up of any number of sub-processing sections including as examples, a high frequency halftone processor 20, a low frequency halftone processor 22, a line/text processor 24, and a contone processor 26. The sub-processing sections within the image processing section 14 perform image processing operations on the same block of image pixels as does the image property classifying section 12. Each image sub-processing section performs image processing operations that are adapted to improve the image quality of a distinct class of imagery.
The third module of the prior art automatic segmentation system shown in FIG. 1 is a control section 28 that uses the information derived from the image classifying section 12 to control the flow of processed image data generated by the image processing section 14. The control section 28 essentially functions as a multiplexer and selects the proper processed image data from among the sub-processing sections 20-26 for delivery to an output buffer 29 according to the image classification determined by the image classifying section 12.
The decision as to what class of imagery the image data belongs to is typically binary in nature. For example, in a conventional image segmentation scheme, the image property classifying section 12 classifies image data as one of three broad classes of imagery including halftone of various frequencies, text, and continuous tone. Depending on those classifications, the image data is processed according to the particular properties of that class of imagery using a range of well known various techniques and algorithms. As an example, if the data is determined to be high frequency halftone, that data is low pass filtered and then re-screened. When the data is determined to be low frequency halftone data, it is compared against a random threshold value. According to another technique, when the decision as to which of the three broad classes of imagery the data belongs is based on a single image property such as peak count of the input image data, the resulting image classification decision is made by thresholding the peak count into three classes of imagery.
Consequently, the control section 28 decides the type of image processing that is required by the image data depending on the decision made by the classification section 12. Thus, the output of the classification section 12 is quantized to one of three broad possibilities with finer classifications, e.g. high/low frequency halftone, as necessary. The control section 28 selects the output for delivery to the output buffer 29 from one of the four image sub-processing sections 20-26 based upon this classification.
In conventional image classification systems, the classifying information is gathered over a context of many pixels and typically changes gradually. However, during the process of comparing this classifying information with one or more classification thresholds, abrupt changes in the classes of blocks of pixels often occur. Abrupt decision making produces a forced choice among several distinct alternative choices and is a primary reason for the formation of visible artifacts in the resulting output image. Most transition points or thresholds are selected so that an image can be classified as one class of imagery with a high degree of certainty. However, some blocks of pixels cannot easily be classified into the several broad groups of imagery types with such certainty because the blocks span multiple transition points or they span a transition zone between different image types.
As noted above, algorithms for classifying image pixels according to document type such as, for example, text, contone, and halftone make their decision based on image context in the vicinity of the pixel being classified. Typically, tiled rectangular blocks of the document are analyzed with the result of the analysis being used to classify all pixels within that block as a single image type.
FIG. 2 illustrates a plurality of tiled rectangular blocks 30, 32, 34, and 36 within a document 38 that was processed to identify the imagery types using any one of the prior art classification schemes described above. As shown, each of the plurality of tiled rectangular blocks 30-36 includes an equal number of pixels 40, 42, 44, 46 because the blocks are arranged in regularly repeating rows and columns within the document image 38. Further as shown in FIG. 2, the size of each of the plurality of rectangular blocks 30-36 is typically selected to be large enough to hold several halftone cells 50, 52, 54, and 56 so that halftone images can be formed by the rendering device after the data is processed.
Generally, the regularly repeating rows and columns of tiled rectangular blocks are necessitated by the algorithms used to classify image pixels according to document type. The algorithms examine the image context around each pixel. As an example, in order to reliably detect the presence of a halftone pattern and produce sufficient information to guide downstream processing, a context covering several halftone cells 50-56 is required. A 65 LPI halftone cell covers a 10.times.10 pixel area in an image sampled at 600 SPI. A 141 LPI halftone cell covers about 3.times.3 pixels. In order to provide this context and ensure the ability to classify the image pixels according to document type, the images are typically analyzed over tiled rectangular blocks 30-36 whose boundaries are fixed relative to the edges of the document image 38. For each block, the results of analyzing the video in the block are used to classify all of the pixels 40-46 in that respective block 30-36. Although it is desirable for these blocks 30-36 to be as small as possible, they must, as a practical matter, contain several halftone cells 50-56 if the document noise is not to be falsely detected as a halftone and for the halftone frequency to be accurately determined. An example of a typical rectangular block size is a 1 mm sq.
Classification based on information derived from tiled blocks results in pixel classification changing at the block boundaries, which is unlikely to be the correct place. As shown in FIG. 2 in somewhat exaggerated form, the first rectangular block 30 lies entirely within a non-halftone region 60 of the document image 38. The second, third, and fourth rectangular blocks 32-36 each lie more or less across the boundary 64 between the non-halftone region 60 and the halftone region 62 of the document image 38. Since all of the pixels 42 in the second rectangular block 32, as an example, will be classified as either being halftone or non-halftone pixels, those pixels that are misclassified and extend over the boundary 64 will contribute to the overall rectangular artifacts generated in the reprographic system, since inappropriate processing will have been applied to an area with rectangular boundaries rather to an area with the natural boundary 64. Similarly with respect to the third and fourth group of pixels 44, 46, in the third and fourth rectangular blocks 34, 36, those pixels that extend over the boundary 64 are classified together with the remaining pixels in their respective blocks. This tends to cause rectangular artifacts in the image.
It is therefore desirable to provide a system that enables a pixel-level override of halftone detection within classification blocks to reduce rectangular artifacts generated in a reprographic system.